---
title:  Data Structure Basics pt.6
description: >
  Strengths and weaknesses of some data structures.
categories: posts
tags: [data-structures, ruby]
---

<details markdown="1" id="table-of-contents">
<summary>
Table of Contents
</summary>

* TOC
{:toc}
</details>

## Review

Over the course of the Data Structure Basics series we talked at an introductory
level about:

- [Basic concepts and definitions]({{site.url}}/posts/data-structure-basics-1){:rel="noopener"}.
- [Arrays]({{site.url}}/posts/data-structure-basics-2){:rel="noopener"}.
- [Lists, stacks, and queues]({{site.url}}/posts/data-structure-basics-3){:rel="noopener"}.
- [Associative arrays]({{site.url}}/posts/data-structure-basics-4){:rel="noopener"}.
- [Tree data structures]({{site.url}}/posts/data-structure-basics-5){:rel="noopener"}.

## Choosing Data Structures

These are a few things about the data we deal with that we should always keep in
mind when choosing data structures:

- How much data do we have?
- How often does it change?
- Does it need to be kept sorted?
- and so on.

However complex we get, these questions will drive our decision. We need to get
passed the 'which data structures are fast' question.
Instead, we should consider the situation we are dealing with to figure out if we
want speed in accessing a direct object, searching, inserting, deleting, sorting,
or what have you, because those are the key question.

Which data structure we choose hardly impacts the performance of our system when
we only deal with trivial amounts of data. But as we gather data and we need
to perform thousands of operations per second choosing the right data structure
becomes quite relevant. Here are a few thing to keep in mind when choosing.

## Arrays

| Strengths | Weaknesses |
|---|---|
| Direct indexing | Sorting and seaching |
| Easy to create and use | Inserting and deleting <br> particularly if not at start/end |

## Linked Lists

| Strengths | Weaknesses |
|---|---|
| Inserting and deleting elements | Direct access <br> requires traversal of the list |
| Iterating through the collection | Searching and sorting <br> (same as direct access) |

## Stacks and Queues

| Strengths | Weaknesses |
|---|---|
| Design for LIFO/FIFO | Direct access |
| | Searching and sorting |

## Hash Tables

| Strengths | Weaknesses |
|---|---|
| Speed of insertion and deletion | Some overhead |
| Speed of access | Retrieving in a sorted order |
| | Searching for a specific value |

## Sets

| Strengths | Do not use for |
|---|---|
| Checking existence | Direct access |
| Avoiding duplicates | |

## Binary Search Trees

| Strengths | Weaknesses |
|---|---|
| Speed for insertion and deletion | Some overhead |
| Speed of access | |
| Maintaining sorted order | |


Other things to consider are:

- Fixed structures are faster and smaller.
- Choose fixed (immutable) structures whenever is possible.
- Use mutable structures so you can load it up with unpredictable amounts of data.
  Consider then copying it into an immutable one if all you need to do from then
  on is only accessing the data.
